1. Field of the Invention
The present invention is related to computer graphics hardware for which OPENGL (GRAPHICS LIBRARY) software is an interface thereto, and, in particular, to improving by diagonal level-of-detail calculations texture locality for pixel quads stored in a texture cache of the computer graphics hardware.
2. Description of the Related Art
Interactive graphics display, in general, is explained in Computer Graphics: Principles and Practices, Foley, vanDam, Feiner, and Hughes, Addison-Wesley, 1992, and in Principles of Interactive Computer Graphics, William M. Newman and Robert F. Sproull, Second Edition, McGraw-Hill Book Company, New York, 1979. Interactive graphics display generally includes a frame buffer storing pixels (or picture elements), a display, and a display controller that transmits the contents of the frame buffer to the display.
The OpenGL graphics system is a software interface to graphics hardware, and is explained in the OpenGL Programming Guide, The Official Guide to Learning OpenGL, Second Edition, Release 1.1, by the OpenGL Architecture Review Board, Jackie Neider, Tom Davis, Mason Woo, Addison-Wesley Developers Press, Reading, Mass., 1997, in the OpenGL Programming Guide, The Official Guide to Learning OpenGL, Release 1, by the OpenGL Architecture Review Board, Jackie Neider, Tom Davis, Mason Woo, Addison-Wesley Publishing Company, Reading, Mass., 1993, and in the OpenGL Reference Manual, The Official Reference Document for OpenGL, Release 1, the OpenGl Architecture Review Board, Addison-Wesley Publishing Company, Reading, Mass., 1993.
A computer model for interpretation of OpenGL commands is a client-server model. An application program being executed by one computer, typically the client computer, issues commands, which are interpreted and processed by another computer, typically the server computer, on which OpenGL is implemented. The client may or may not operate on the same computer as the server. A computer, then, can make calls through an OpenGL software interface to graphics hardware, and the graphics hardware can reside either on the same computer making the calls or on a remote computer.
A tool for describing how data is processed in OpenGL is a processing pipeline. The OpenGL processing pipeline 10 shown in FIG. 1 receives commands, and may store the commands for future processing in a display list 14 or execute the commands immediately. The OpenGL processing pipeline includes an evaluator 16, which approximates curve and surface geometry by evaluating polynomial commands of the input values; per-vertex operations and primitive assembly 18, in which geometric primitives such as points, line segments, and polygons, described by vertices, are processed, such as transforming and lighting the vertices, and clipping the primitives into a viewing volume; rasterization 20 produces a series of frame buffer addresses and associated values, and converts a projected point, line, or polygon, or the pixels of a bitmap or image, to fragments, each corresponding to a pixel in the framebuffer; per-fragment operations 22 performs operations such as conditional updates to the frame buffer 24 based on incoming and previously stored depth values (to effect depth buffering) and blending of incoming pixel colors with stored colors, masking, and other logical operations on pixel values. The final pixel values are then stored in the frame buffer 24.
Pixel operations 26 processes input data from the commands 12 which is in the form of pixels rather than vertices. The result of the pixel operations 26 is stored in texture memory 28, for use in rasterization 20. The resulting fragments are merged into the frame buffer 24 as if the fragments were generated from geometric data.
In addition, if texturing is enabled during rasterization 20, a texel is generated from texture memory 28 for each fragment and applied to the fragment. A texel is a texture element obtained from texture memory and represents the color of the texture to be applied to a corresponding fragment. Texturing maps a portion of a specified texture image onto each primitive. Texture mapping is accomplished by using the color (Red (R), Green (G), Blue (B), or Alpha (A)) of the texture image at the location indicated by the fragment's (s, t, and r) coordinates. In the case of a 2-dimensional image (2-D image), s and t coordinates are applicable, and in the case of a 3-dimensional image (3-D image), then s, t, and r coordinates are applicable.
OpenGL provides a way to specify the details of how texturing of a primitive is effected. These details include specification of the image to be texture mapped, the means by which the image is filtered when applied to the primitive, and the function that determines what RGBA value is produced given a fragment color and an image value. A command specifying the target, level, internal format, width, height, border, format, type, and *data (a pointer to the data) is used to specify the texture image in GL commands such as TexImage2D or TexImage1D. The level argument is an integer level-of-detail number. The main texture image has a level of detail number of 0, and if a level of detail less than 0 is specified, an error message is generated.
The maximum allowable width or height of the image is an implementation dependent function of the level of detail and internal format of the resulting image array. An image with zero height or width indicates the null texture. If the null texture is specified for level of detail zero, it is as if texturing were disabled.
The image indicated to the GL (or graphics library) by the image pointer is decoded and copied into the GL's internal memory. This copying effectively places the decoded image inside a border of the maximum allowable width, which is currently 1, whether or not a border has been specified.
An example of a texture image 29 and the coordinates used to access it is shown in FIG. 2. FIG. 2 shows a two-dimensional texture image with n.times.m dimensions of n=3 and m=2. A one-dimensional texture would comprise a single strip. The values, .alpha. and .beta., used in blending adjacent texels to obtain a texture value are also shown. As shown in FIG. 2, values of s and t coordinates are each in the range of 0.0 to 1.0.
If no border or a border smaller than the maximum allowable width has been specified, then the image is still stored as if it were surrounded by a border of the maximum possible width. Any excess border (which surrounds the specified image, including any border) is assigned unspecified values. A one-dimensional texture has a border only at its left and right ends.
The decoded image is referred to as the texture array. A two-dimensional texture array has width w.sub.t =2.sup.n +2b.sub.t and height h.sub.t =2.sup.m +2b.sub.t, where b.sub.t is the maximum allowable border width; and a one-dimensional texture array has width w.sub.t =2.sup.n +2b.sub.t and height h.sub.t =1.
Texturing, including determination of the level of detail and selection of a mipmap, of the related art is now discussed, with reference being made to OpenGL commands using the OpenGL command syntax.
Object coordinates (x, y, z, and w) and texture coordinates (s, t, r, and q) are provided for each vertex.
A texel is an element (i, j) of the texture array (for a 1-dimensional array, j is irrelevant). The texture value used in texturing a fragment is determined by that fragment's associated (s, t) coordinates, but as shown in FIG. 2 may not correspond to any actual texel.
Typically, there are 8 neighboring texels for each pixel, which means that 8 texels encompass or surround each pixel.
Texture images may also be specified using image data taken directly from the framebuffer, and rectangular subregions of existing texture images may be respecified.
If texture wrapping for the s or t coordinates is set to be repeated (by setting parameters such as TEXTURE_WRAP_S or TEXTURE_WRAP_T to REPEAT), then the GL ignores the integer part of the s or t coordinates, respectively, using only the fractional part. For a number r, the fractional part is r-.left brkt-bot.r.right brkt-bot., regardless of the sign of r, and the floor function truncates towards -.infin.. The parameter CLAMP causes s or t coordinates to be clamped to the range [0,1]. The initial state is for both s and t behavior to be that given by the repeat value.
Applying a texture to a primitive implies a mapping from texture image space to framebuffer image space. In general, this mapping involves a reconstruction of the sampled texture image, followed by a projective warping implied by the mapping to framebuffer space, then a filtering, followed finally by a resampling of the filtered, warped, reconstructed image before applying it to a fragment.
In the GL, this mapping is approximated by one of two simple filtering schemes. One of these schemes is selected based on whether the mapping from texture space to framebuffer space is deemed to magnify or minify the texture image. The choice is governed by a scale factor .rho.(x, y) and .lambda.(x, y).tbd.log.sub.2 [.rho.(x, y)]; if .lambda.(x, y) is less than or equal to a constant (the selection of the constant is described herein below) the texture is said to be magnified; if it is greater, the texture is minified. .lambda. is referred to as the level of detail.
Let s(x, y) be the function that associates an s texture coordinate with each set of window coordinates (x, y) that lie within a primitive, and t(x, y) be defined analogously. Let u(x, y)=2.sup.n s(x, y) and v(x, y)=2.sup.m t(x, y) (for a one-dimensional texture, define v(x, y).tbd.0). For a polygon, .rho. is given at a fragment with window coordinates (x, y) by ##EQU1##
where .differential.u/.differential.x indicates the derivative of u with respect to window x, and similarly for the other derivatives. Equation (1) is rotationally invariant, which means that if the image is rotated around, the same level of detail is provided. However, equation (1) is very compute-intensive.
For a line, the formula is ##EQU2##
where .DELTA.x=x.sub.2 -x.sub.1 and .DELTA.y=y.sub.2 -y.sub.1 with (x.sub.1,y.sub.1) and (x.sub.2,y.sub.2) being the segment's window coordinate endpoints and l=.DELTA.x.sup.2 +L +.DELTA.y.sup.2 +L . For a point, pixel rectangle, or bitmap, .rho..tbd.1.
While equations (1) and (2) give the best results when texturing, they are often impractical to implement. Therefore, an implementation may approximate the ideal .rho. with a function f(x, y) subject to these conditions:
1. f(x, y) is continuous and monotonically increasing in each of .vertline..differential.u/ .differential.y.vertline.,.vertline..differential.v/ .differential.x.vertline., and .vertline..differential.v/.differential.y.vertline., PA1 2. Let ##EQU3##
Then max {m.sub.u,m.sub.v }.ltoreq.f(x,y).ltoreq.m.sub.u +m.sub.v. Max{m.sub.u,m.sub.v } is the rectangular level of detail calculation, and m.sub.u +m.sub.v is the fuzziest permissible limit, but is very fuzzy.
When .lambda. indicates minification, the value assigned to the TEXTURE_MIN_FILTER parameter is used to determine how the texture value for a fragment is selected. When TEXTURE_MIN_FILTER is NEAREST, the texel nearest (in Manhattan distance) to that specified by (s,t) is obtained. This means the texel at location (i,j) becomes the texture value, with i given by ##EQU4##
If TEXTURE_WRAP_S is REPEAT, then 0.ltoreq.s&lt;1. Similarly, j is found as ##EQU5##
For a one-dimensional texture, j is irrelevant; the texel at location i becomes the texture value.
When TEXTURE_MIN_FILTER is LINEAR a 2.times.2 square of texels is selected. This square is obtained by first computing ##EQU6## and ##EQU7## Then ##EQU8## and EQU Let EQU .alpha.=frac(u-1/2) EQU and EQU .beta.=frac(v-1/2) ##EQU9##
where frac(x) denotes the fractional part of x. Let .tau..sub.ij be the texel at location (i,j) in the texture image. Then the texture value, .tau. is found as EQU .tau.=(1-.alpha.)(1-.beta.).tau..sub.iojo +.alpha.(1-.beta.).tau..sub.iojo +(1-.alpha.).beta..tau..sub.iojo +.alpha..beta..tau..sub.ij (5)
for a two-dimensional texture.
For a one-dimensional texture, EQU .tau.=(1-.alpha.).tau..sub.io +.alpha..tau..sub.i1 (6)
where .tau..sub.i indicates the texel at location i in the one-dimensional texture. If any of the selected .tau..sub.ij (or .tau..sub.i) in the above equations refer to a border texel with i&lt;-b.sub.s, j&lt;-b.sub.s, i.gtoreq.w.sub.s -b.sub.s, or j.gtoreq.h.sub.s -b.sub.s, then the border color given by the current setting of the parameter TEXTURE_BORDER_COLOR is used instead of the unspecified value or values.
The RGBA values of the TEXTURE_BORDER_COLOR are interpreted to match the texture's internal format in a manner consistent with Table 1.
TABLE 1 Base Internal RGBA Texture Format Values Components ALPHA A A LUMINANCE R L LUMINANCE ALPHA R,A L,A INTENSITY R I RGB R,G,B R,G,B RGBA R,G,B,A R,G,B,A
OpenGL parameters of TEXTURE_MIN_FILTER, including NEAREST_MIPMAP_NEAREST, NEAREST_MIPMAP_LINEAR, LINEAR_MIPMAP_NEAREST, and LINEAR_MIPMAP_LINEAR, each require the use of a mipmap. A mipmap is an ordered set of arrays representing the same image; each array has a resolution lower than the previous one. If the texture has dimensions 2.sup.n.times.2.sup.m, then there are max{n,m}+1 mipmap arrays. The first array is the original texture with dimensions 2.sup.n.times.2.sup.m. Each subsequent array has dimensions 2.sup.(k-1).times.2.sup.(l-1) where 2.sup.k.times.2.sup.1 are the dimensions of the previous array. This is the case as long as both k&gt;0 and 1&gt;0. Once either k=0 or l=0, each subsequent array has dimension 1.times.2.sup.(l-1) or 2.sup.(k-1).times.1, respectively, until the last array is reached with dimension 1.times.1.
Each array in a mipmap is transmitted to the GL using TexImage2D or TexImage1D; the array being set is indicated with the level-of-detail argument. Level-of-detail numbers proceed from 0 for the original texture array through p=max{n,m} with each unit increase indicating an array of half the dimensions of the previous one as already described. If texturing is enabled (and TEXTURE_MIN_FILTER is one that requires a mipmap) at the time a primitive is rasterized and if the set of arrays 0 through p is incomplete, based on the dimensions of array 0, then it is as if texture mapping were disabled. The set of arrays 0 through p is incomplete if the internal formats of all the mipmap arrays were not specified with the same symbolic constant, or if the border widths of the mipmap arrays are not the same, or if the dimensions of the mipmap arrays do not follow the sequence described above. Arrays indexed greater than p are insignificant.
The mipmap is used in conjunction with the level of detail to approximate the application of an appropriately filtered texture to a fragment.
Let p=max{n,m} and let c be the value of .lambda. at which the transition from minification to magnification occurs, and, for minification, values of .lambda. where .lambda.&gt;c are applicable. For the NEAREST_MIPMAP_NEAREST parameter, if c&lt;.lambda..ltoreq.0.5 then the mipmap array with level-of-detail of 0 is selected. Otherwise, the dth mipmap array is selected when d-1/2&lt;.lambda..ltoreq.d+1/2 as long as 1.ltoreq.d.ltoreq.p. If .lambda.&gt;p+1/2, then the pth mipmap array is selected. The rules for NEAREST are then applied to the selected array.
The same mipmap array selection rules apply for LINEAR_MIPMAP_NEAREST as for NEAREST_MIPMAP_NEAREST, but the rules for LINEAR are applied to the selected array.
For NEAREST_MIPMAP_LINEAR, the level d-1 and the level d mipmap arrays are selected, where d-1.ltoreq..lambda.&lt;d, unless .lambda..gtoreq.p, in which case the pth mipmap array is used for both arrays. The rules for NEAREST are then applied to each of these arrays, yielding two corresponding texture values .tau..sub.d-1 and .tau..sub.d. The final texture value is then found as EQU .tau.=[1-frac(.lambda.)].tau..sub.d-1 +frac(.lambda.).tau..sub.d. (7)
LINEAR_MIPMAP_LINEAR has the same effect as LINEAR_MIPMAP_LINEAR except that the rules for LINEAR are applied for each of the two mipmap arrays to generate .tau..sub.d-1 and .tau..sub.d.
Texture magnification is now explained. When .lambda. indicates magnification, the value assigned to TEXTURE_MAG_FILTER determines how the texture value is obtained. There are two possible values for TEXTURE_MAG_FILTER: NEAREST and LINEAR. NEAREST behaves exactly as NEAREST for TEXTURE_MIN_FILTER (equation (3) and (4) are used); LINEAR behaves exactly as LINEAR for TEXTURE_MIN_FILTER (equation (5) is used). The level-of-detail 0 texture array is always used for magnification.
In addition, there is a choice of c, the minification vs. magnification switch-over point. If the magnification filter is given by LINEAR and the minification filter is given by NEAREST_MIPMAP_NEAREST or NEAREST_MIPMAP_LINEAR, then c=0.5. This is done to ensure that a minified texture does not appear "sharper" than a magnified texture. Otherwise, c=0.
Multiple levels of detail in OpenGL allow textured objects to be viewed at different distances from a viewpoisnt by determining which of the mipmap images in a pyramid of mipmaps of the same image to select, and by filtering between 2 levels of detail to minimize aliasing artifacts.
Mipmapping prevents aliasing in texel space and eliminates aliasing artifacts by blurring between levels of detail, one of which is not aliasing and the other of which is slightly aliasing. For example, a brick wall would appear as noise without aliasing if a full resolution image of the brick wall were to be applied to a brick wall that is far enough from the viewer to appear as a single pixel.
In the related art, if magnification or minification is selected, and if the parameter GL_LINEAR is selected, a weighted linear average of the 2.times.2 array of texels that lies nearest to the center of the pixel is used.
In standard OpenGL (which is also referred to as GL), the quality of a displayed image ranges between fuzzy and sharp.
To obtain a sharp image, the level of detail is calculated in the related art using the rectangular maximum absolute difference of the s and t coordinates. In the related art, for the 2 adjacent coordinates in the x and y directions, the s and t coordinates are calculated, and the maximum absolute difference horizontally and vertically of the s and t coordinates is determined. Accordingly, in standard GL, the level of detail is equal to log.sub.2 row.
To obtain a fuzzy image in the related art, different level of detail calculations are performed, such as calculating the sum of the maximum absolute values of the s and t coordinates. In the related art, the level of detail value must fall between the rectangular level of detail and the sum of the maximum of the absolute values. As explained herein above, max{m.sub.u,m.sub.v } is the rectangular level of detail calculation, and m.sub.u +m.sub.v is the fuzziest permissible limit, but is very fuzzy.
Traditional level of detail calculations of the related art require a 5.times.5 texel footprint to be stored in texture memory to provide a sufficient number of texels for texturing of each 2.times.2 region of pixels stored in the framebuffer. Each 2.times.2 region of pixels stored in the framebuffer is referred to as a quad. A 5.times.5 texel footprint is required because the traditional level of detail calculations involve determining the rectangular absolute difference of texture coordinates. However, requiring a 5.times.5 texel footprint is an inefficient use of hardware, because most computer systems are optimized to manipulate 2.sup.n numbers, where n is a whole number.
A problem in the related art is that for each pixel within the quad of pixels, processing must include the s and t coordinates and the level of detail for each of the 8 texels surrounding the s and t coordinates at that pixel.
A further problem of the related art is that a large amount of texture memory is required to store the s and t coordinates and the level of detail corresponding to each pixel for each of the four or eight neighbors of that pixel.